package leetcode_2301_2400;

import java.util.*;

public class LeeCode_2318 {
    public static void main(String[] args) {
        System.out.println(distinctSequences(2));
        System.out.println(distinctSequences(3));
        System.out.println(distinctSequences(4));
        System.out.println(distinctSequences(1));
    }
    private static int distinctSequences(int n) {
        if (n == 1)
            return 6;
        long mod = (long) (1e9 + 7);
        Map<Integer, Set<Integer>> m1 = new HashMap<>();
        for (int i = 1; i <= 6; i++) {
            Set<Integer> list = new HashSet<>();
            for (int j = 1; j <= 6; j++) {
                if (i == j)
                    continue;
                if (gcd(i, j) == 1){
                    list.add(j);
                }
            }
            m1.put(i, list);
        }
        Map<Long, Set<Integer>> m2 = new HashMap<>();
        for (Integer fir : m1.keySet()) {
            Set<Integer> ns = m1.get(fir);
            for (Integer next : ns) {
                int key = fir * 7 + next;
                Set<Integer> vals = m1.get(next);
                Set<Integer> son = new HashSet<>(vals);
                son.remove(fir);
                son.remove(next);
                m2.put((long) key, son);
            }
        }
        Deque<long[]> deque = new ArrayDeque<>();
        for (int i = 1; i <= 6; i++) {
            for (Integer next : m1.get(i)) {
                deque.offer(new long[]{i * 7 + next, 1});
            }
        }
        n -= 2;
        while (n > 0){
            Map<Long, Long> tmp = new HashMap<>();
            while (!deque.isEmpty()){
                long[] p = deque.pop();
                long key = p[0], count = p[1], pre = p[0] % 7;
                if (pre == 0)
                    System.out.println();
                if(!m2.containsKey(key))
                    System.out.println();
                for (Integer next : m2.get(key)) {
                    long k = pre * 7 + next;
                    if (k == 1)
                        System.out.println();
                    tmp.put(k, (tmp.getOrDefault(k, 0L) + count) % mod);
                }
            }
            for (Long k : tmp.keySet()) {
                deque.offer(new long[]{k, tmp.get(k)});
            }
            n--;
        }
        long ans = 0;
        while (!deque.isEmpty()){
            ans += deque.poll()[1];
            ans %= mod;
        }
        return (int) ans;
    }
    private static int gcd(int x, int y){
        while (x != 0){
            int tmp = x;
            x = y % x;
            y = tmp;
        }
        return y;
    }
}